package com.ryujung.linked_list.leetCode_21;

/*

Merge two sorted linked lists and return it as a new list. 
The new list should be made by splicing together the nodes of the first two lists.

Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

思路:双指针
两指针分别指向两个链表的头部,并创建一个新的链表,
循环遍历,只要两指针都不为空,就继续遍历
每次从双指针中获取其中小的放入新链表中,
然后被获取的指针向右移动,再次循环

时间复杂度:O(m+n) 遍历所有节点
空间复杂度:O(1) 迭代的过程只会产生几个指针，所以它所需要的空间是常数级别的。
*/
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode(-1);//哨兵节点,用于返回结果链表的头节点
        ListNode temp =sentinel;//指针,最开始指向哨兵

        //在循环中,将指针的next值指向两节点中较小的节点
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                temp.next = l1;
                l1 = l1.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        //只剩下某一个链表不为空
        temp.next = l1==null?l2:l1;

        return sentinel.next;
    }
}

//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
